package com.ddshuai.easy;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 * <p>
 * 括号必须以正确的顺序关闭，"()" 和 "()[]{}" 是有效的但是 "(]" 和 "([)]" 不是。
 *
 * @author admin
 */
public class ValidBracket {

    public static boolean isValidBracket(String s) {
        Map<Character, Character> bracket = new HashMap<>(3);
        bracket.put('}', '{');
        bracket.put(')', '(');
        bracket.put(']', '[');

        //还是按照栈的方式处理最简单
        if (s == null) {
            return true;
        }
        //has start bracket
        boolean hasBracket = false;

        char[] chars = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        ArrayDeque<Character> deque = new ArrayDeque<>();

        for (int i = 0; i < chars.length; i++) {
            //如果上来就是关闭的括号直接就GG
            if (bracket.containsKey(chars[0])) {
                return false;
            }

            if (bracket.containsKey(chars[i])) {
                //遇到了关闭的 但是 都还没有开始的 直接结束
                if (!hasBracket) {
                    return false;
                }
                //结束的各种括号
                deque.offer(chars[i]);


            } else {
                //如果加入的时候前面已经有完整的括号组合 先出栈掉
                if (deque.size() > 0) {
                    if (stack.size() < deque.size()) {
                        return false;
                    }

                    //出列
                    while (!deque.isEmpty()) {
                        Character close = deque.poll();
                        Character start = stack.pop();

                        //一个没有匹配上 就是不符合规则的
                        if (!bracket.get(close).equals(start)) {
                            return false;
                        }
                    }
                }
                //开始的各种括号
                stack.push(chars[i]);

                if (!hasBracket) {
                    hasBracket = true;
                }

            }

        }
        //循环之后 内层的组合应该已经清理干净了 最后处理一波
        if (stack.size() != deque.size()){
            return false;
        }else {
            while (!deque.isEmpty()) {
                Character close = deque.poll();
                Character start = stack.pop();

                //一个没有匹配上 就是不符合规则的
                if (!bracket.get(close).equals(start)) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 解答人中耗时最短的
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char c,temp;
        for (int i = 0; i < s.length(); i++) {
            c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
                continue;
            }
            if (stack.size() == 0) {
                return false;
            }
            temp = stack.pop();
            switch (c){
                case ')':{
                    if (temp != '(') {
                        return false;
                    }
                    break;
                }
                case ']':{
                    if (temp != '[') {
                        return false;
                    }
                    break;
                }
                case '}':{
                    if (temp != '{') {
                        return false;
                    }
                    break;
                }
                default:
                    return false;
            }
        }
        if (stack.size() != 0) {
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isValidBracket("{(){[]}}"));

    }
}
